/**
 * 矩阵置零
 *
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 * 示例 1：
 * 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：[[1,0,1],[0,0,0],[1,0,1]]
 *
 * 示例 2：
 * 输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
 * 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
 *
 * 提示：
 * m == matrix.length
 * n == matrix[0].length
 * 1 <= m, n <= 200
 * -231 <= matrix[i][j] <= 231 - 1
 *
 * 进阶：
 * 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个仅使用常量空间的解决方案吗？
 */

import java.util.Arrays;

/**
 * 这一题的难点就在于我们要修改的数后面也会变为 零, 这样我们后面在碰到他的时候还要
 * 再去 置零
 * 1. 要是我们使用 一个 额外的数组记录我们院本数组中的 0 , 然后再开始
 * 矩阵置零, 那这一题是没有任何难度的
 * 空间复杂度 : O(m * n)
 *
 * 2. 我们进阶一点, 我们先不修改原数组中的值, 先记录下我们要修改的行和列
 * 最后在一起修改, 这样可以降低我们的时间复杂度
 * 空间复杂度 : O(m + n)
 *
 * 3.空间复杂度 为 1 的方法实际上就是我们用给的数组作文章, 我们用 matrix
 * 的 第一行 和 第一列 作为标记, 然后后续只需要用第一行和第一列的值作判断就
 * 可以了, 但是还有一个特殊的点, 就是我们的第一行和第一列肯定会在后面的判断
 * 中被无情给全置为 0 , 所以我们可以用两个数来作为标记, 标记第一行和第一列
 * 是否全为 0
 * 时间复杂度 : O(m * n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 方法二
    public void setZeroes(int[][] matrix) {

        int m = matrix.length, n = matrix[0].length;

        // 两个数组作为标记

        // 行标记
        boolean[] tmp1 = new boolean[m];

        // 列标记
        boolean[] tmp2 = new boolean[n];

        // 循环一次给 tmp1 和 tmp2 赋值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j  < n; j++) {
                if (matrix[i][j] == 0) {
                    tmp1[i] = true;
                    tmp2[j] = true;
                }
            }
        }

        // 开始置为 0
        for (int i = 0; i < m; i++) {
            if (tmp1[i]) {
                Arrays.fill(matrix[i], 0);
            }
        }

        for (int j = 0; j < n; j++) {
            if (tmp2[j]) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}